package A1动态规划;

public class LC_416分割等和子集 {
    public static void main(String[] args){
        int[] nums={1,5,11,5};
        System.out.println(canPartition(nums));
    }
    public static boolean canPartition(int[] nums) {
        int n=nums.length;
        int sum=0;
        for(int i=0;i<n;i++)
            sum+=nums[i];
        if(sum%2!=0)
            return false;
        int target=sum/2;
        int[] dp=new int[target+1];//dp大小为背包容量加一
        dp[0]=0;
        for(int i=0;i<n;i++)
            for(int j=target;j>=nums[i];j--)
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
        return dp[target]==target;//dp数组值与目标值大小一致则为true
    }
}
